﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using Library.Linq;
using INDEX = System.UInt64;

namespace Library.Collections.Generic
{
    [DebuggerDisplay("Count={Count}")]
    public sealed class Queue<T> : IQueue<T>, IQueue, IClearable, IFirst<T>, IElementAt<T>, ILast<T>
    {
        struct Enumerator : IEnumerator<T>, System.Collections.IEnumerator, IDisposable
        {
            Queue<T> queue;
            long index;
            INDEX version;

            internal Enumerator(Queue<T> queue)
            {
                this.queue = queue;
                index = -2;
                version = queue.version;
            }

            public void Dispose()
            {
                index = -2;
            }

            public bool MoveNext()
            {
                if (version != queue.version)
                    throw new InvalidOperationException();

                if (index == -2)
                    index = (long)queue.count;

                return index != -1 && --index != -1;
            }

            public T Current
            {
                get
                {
                    if (index < 0)
                        throw new InvalidOperationException();

                    return queue.data[(queue.count - 1 - (INDEX)index + queue.head) % (INDEX)queue.data.Length];
                }
            }

            void System.Collections.IEnumerator.Reset()
            {
                if (version != queue.version)
                    throw new InvalidOperationException();

                index = -2;
            }

            object System.Collections.IEnumerator.Current
            {
                get { return Current; }
            }
        }

        public Queue()
        {
            data = new T[0];
        }
        public Queue(INDEX capacity)
        {
            data = new T[capacity];
        }
        public Queue(IEnumerable<T> enumerable)
        {
            if (enumerable == null)
                throw new ArgumentNullException("enumerable");

            ICountable countable = enumerable as ICountable;
            INDEX size = countable != null ? countable.Count : 0;

            data = new T[size];

            foreach (T item in enumerable)
                Enqueue(item);
        }

        T[] data;
        INDEX head;
        INDEX tail;
        INDEX count;
        INDEX version;

        public bool Enqueue(T item)
        {
            if (count == (INDEX)data.Length || tail == (INDEX)data.Length)
                SetCapacity(Math.Max(Math.Max(count, tail) * 2, 4));

            data[tail] = item;

            if (++tail == (INDEX)data.Length)
                tail = 0;

            count++;
            version++;

            return true;
        }

        public bool Dequeue(out T item)
        {
            if (count == 0)
            {
                item = default(T);
                return false;
            }
            item = data[head];
            data[head] = default(T);
            if (++head == (INDEX)data.Length)
                head = 0;
            count--;
            version++;
            return true;
        }

        public bool Peek(out T item)
        {
            if (count == 0)
            {
                item = default(T);
                return false;
            }
            item = data[head];
            return true;
        }

        public bool Contains(T item)
        {
            INDEX index = this.head;
            INDEX counter = this.count;
            if (item == null)
            {
                while (counter-- > 0)
                {
                    if (this.data[index] == null) return true;
                    index = (index + 1) % (INDEX)this.data.Length;
                }
            }
            else
            {
                while (counter-- > 0)
                {
                    var current = this.data[index];
                    if (current != null && current.Equals(item)) return true;
                    index = (index + 1) % (INDEX)this.data.Length;
                }
            }
            return false;
        }

        public INDEX Count
        {
            get
            {
                return count;
            }
        }

        public bool Clear()
        {
            Array.Clear(data, 0, data.Length);
            head = tail = count = 0;
            version++;
            return true;
        }

        void SetCapacity(INDEX capacity)
        {
            if (capacity == (INDEX)data.Length)
                return;

            if (capacity < count)
                throw new InvalidOperationException();

            T[] new_data = new T[capacity];
            if (count > 0)
                CopyTo(new_data, 0);

            data = new_data;
            tail = count;
            head = 0;
            version++;
        }

        void CopyTo(T[] array, INDEX index)
        {
            INDEX length = (INDEX)data.Length;
            INDEX length_from_head = length - head;

            Array.Copy(data, (int)head, array, (int)index, (int)Math.Min(count, length_from_head));
            if (count > length_from_head)
                Array.Copy(data, 0, array, (int)(index + length_from_head), (int)(count - length_from_head));
        }

        public IEnumerator<T> GetEnumerator()
        {
            return new Enumerator(this);
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return new Enumerator(this);
        }

        bool IQueue.Enqueue(object item)
        {
            if (!(item is T)) return false;
            return Enqueue((T)item);
        }

        bool IQueue.Dequeue(out object item)
        {
            T t;
            if (Dequeue(out t))
            {
                item = t;
                return true;
            }
            else
            {
                item = null;
                return false;
            }
        }

        bool IQueueReadOnly.Peek(out object item)
        {
            T t;
            if (Peek(out t))
            {
                item = t;
                return true;
            }
            else
            {
                item = null;
                return false;
            }
        }

        bool IContainer.Contains(object item)
        {
            if (!(item is T)) return false;

            INDEX index = this.head;
            INDEX counter = this.count;
            if (item == null)
            {
                while (counter-- > 0)
                {
                    if (this.data[index] == null) return true;
                    index = (index + 1) % (INDEX)this.data.Length;
                }
            }
            else
            {
                while (counter-- > 0)
                {
                    var current = this.data[index];
                    if (current != null && current.Equals(item)) return true;
                    index = (index + 1) % (INDEX)this.data.Length;
                }
            }
            return false;
        }

        bool IFirst<T>.First(out T item)
        {
            return Peek(out item);
        }

        bool IElementAt<T>.ElementAt(INDEX index, out T item)
        {
            if (index < count)
            {
                item = data[(head + index) % (INDEX)data.Length];
                return true;
            }
            else
            {
                item = default(T);
                return false;
            }
        }

        bool ILast<T>.Last(out T item)
        {
            if (count == 0)
            {
                item = default(T);
                return false;
            }
            item = data[(tail + (INDEX)data.Length - 1) % (INDEX)data.Length];
            return true;            
        }

        public bool IsReadOnly
        {
            get
            {
                return false;
            }
        }
    }
}
